二叉树之二叉查找(搜索)树的查找、插入、删除及遍历(C++实现) |
您所在的位置：网站首页 › 二叉树 复杂度 › 二叉树之二叉查找(搜索)树的查找、插入、删除及遍历(C++实现) |
|
目录
一、认识二叉树查找(搜寻或搜索)树二、二叉查找树的查找算法三、二叉查找树的插入算法四、二叉查找树的删除算法五、二叉查找树的遍历六、二叉查找树的性能优化
一、认识二叉树查找(搜寻或搜索)树
二叉查找树1（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意结点的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；任意结点的左、右子树也分别为二叉查找树；一颗简单的二叉搜索树： 6 4 1 5 10 7 11二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 时间复杂度: 算法平均最坏查找(搜索)O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)空间复杂度：平均O(n), 最坏O(n) 二、二叉查找树的查找算法在二叉搜索树中查找X的过程为： 查找从根结点开始，若二叉搜索树为空，则返回空，否则将根结点的数据域值与X进行比较，并进行相应的处理： 若X等于根结点的数据域值，搜索完成，返回该结点；若X小于根结点的数据域值，则只需在其左子树继续搜索；若X大于根结点的数据域值，则只需在其右子树继续搜索； 重复上述过程查找效率取决于树的高度 定义树结点： //头文件 #include #incldue //包含智能指针 typedef int ElementType; //等价于using xxx = xxxx struct TreeNode { //构造函数 TreeNode() :lchild(nullptr), rchild(nullptr) {}; TreeNode(ElementType d, std::shared_ptr lhs, std::shared_ptr rhs) : data(d), lchild(lhs), rchild(rhs) {}; ElementType data; std::shared_ptr lchild; std::shared_ptr rchild; }; using BinTree = std::shared_ptr; //C++11新增递归(尾递归)实现： BinTree BSTFind(BinTree BT,ElementType X) { //树空，直接搜索结束 if (!BT) { return nullptr; } if (BT->data == X) { return BT; } else if (BT->data > X) { //根据二叉搜索树的特征，X小于根结点搜索其左子树 return BSTFind(BT->lchild, X); } else { //根据二叉搜索树的特征，X大于根结点搜索其右子树 return BSTFind(BT->rchild, X); } }非递归(迭代)实现 BinTree BSTIterFind(BinTree BT, ElementType X) { auto T = BT; while (T) { if (X == T->data) { return T; //查找成功，返回结点 } else if (X data) { T = T->lchild; //进入左子树，继续搜索 } else { T = T->rchild; //进入右子树，继续搜索 } } return nullptr; //查找失败返回空(涵盖空树和搜索完毕无匹配情况) } 三、二叉查找树的插入算法向一个二叉搜索树中插入一个数据为X的结点算法过程为： 若二叉搜索树是空树，则插入一个数据为X 的结点作为根结点并返回根结点给双亲结点(如果存在的话)，否则：将根结点的数据域值与X进行比较，搜索合适的插入位置： 若X小于根结点的数据域值，则只需在其左子树继续搜索；若X大于根结点的数据域值，则只需在其右子树继续搜索；若X等于根结点的数据域值，无需处理，结束插入程序； 重复上述过程递归实现： BinTree BSTInsert(BinTree BT, ElementType X) { auto T = BT; //若树空，直接生成一个结点(满足二叉搜索树的定义)并返回 if (!T) { auto newBST = std::make_shared();//调用无参数版本的构造函数 newBST->data = X; return newBST; } //树非空，搜索合适的插入位置 else { if (X data) { //插入到根结点的左子树 T->lchild = BSTInsert(T->lchild, X); } else if(X>T->data) { //X>T->data,插到根结点的右子树 T->rchild = BSTInsert(T->rchild, X); } //else //{ // //二叉搜索树主要用于构建关联容器(比如C++中的map,set)，需保证键值唯一 // //故插入已存在值时可以给个错误提示或者返回已存在的结点 //} } return T; }非递归实现: BinTree BSTIterInsert(BinTree BT, ElementType X) { auto T = BT; BinTree tmptr = nullptr; //保存结点 int flag=-1; //用于确定插入位置,值为0插在左子树，为1插在右子树 //二叉搜索树非空 while (T) { tmptr = T; if (X data) { T = T->lchild; //小于结点值，进入左子树 flag = 0; } else if(X>T->data) { T = T->rchild; //大于结点值，进入右子树 flag = 1; } else { return T; //插入已有值则直接退出搜索同时返回该结点 } } //空树或者找到插入位置，生成一个结点 T = std::make_shared(); T->data = X; if (flag==0) { tmptr->lchild = T; } if (flag == 1) { tmptr->rchild = T; } return BT; } 四、二叉查找树的删除算法在二叉查找树删去一个结点比较麻烦，需分三种情况讨论： 若需删除结点为叶结点(即无左右子树的结点)，由于删去叶结点不破坏整棵树的结构，故只需修改其双亲结点的指针即可。若需删除结点只有左子树或右子树，此时只要令左子树或右子树直接成为其双亲结点的左子树（当只有左子树）或右子树（当只有右子树）即可，作此修改不会破坏二叉查找树的特性。若需删除结点的左子树和右子树均不空。在删去该结点之后，需保持其它元素之间的相对位置不变，二叉搜索树不被破坏。具体做法是用该结点的左子树中的最大元素或者右子树中的最小元素结点来替代该结点的位置举个栗子： 有一棵二叉搜索树2： 10 2 23 15 29 12 NULL 26 38然后删除 23 结点，删除完的结果有两种: 左子树最大元素15替代23的位置： 10 2 15 12 29 26 38 右子树最小元素26替代23位置： 10 2 26 15 29 12 NULL NULL 38删除算法实现代码： BinTree BSTDelete(BinTree BT, ElementType X) { if (!BT) { //树空，直接返回空 return nullptr; } else if (X data) { //小于则左子树递归删除 BT->lchild = BSTDelete(BT->lchild, X); } else if (X > BT->data) { //大于则右子树递归删除 BT->rchild = BSTDelete(BT->rchild, X); } else { //找到要删除的结点，按情况处理 if (!BT->lchild && !BT->rchild) { //删除叶结点,置空，智能指针将会自动释放内存 BT = nullptr; } else if(BT->lchild && !BT->rchild) //只有左子树，用左子树替代删除结点 { BT = BT->lchild; } else if(!BT->lchild && BT->rchild) //只有右子树。用右子树替代删除结点 { BT = BT->rchild; } else //同时存在左右子树 { //二叉搜索树的最小元素在最左边的左子树，最大元素在最右边的右子树 //这里使用删除结点的左子树最大元素来替代删除结点 auto p = BT->lchild; //找到左子树中最大元素 while (p->rchild) { p = p->rchild; } BT->data = p->data; //删除左子树中最大元素结点 BT->lchild = BSTDelete(BT->lchild, BT->data); } } return BT; } 五、二叉查找树的遍历二叉搜索树的遍历和普通二叉树一样，具体可移步二叉树之前序、中序、后序遍历算法实现以及二叉树之层序遍历算法实现。 六、二叉查找树的性能优化一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。 常见的平衡树有**红黑树、AVL树(自平衡二叉查找树)**等等，有兴趣可以自行查找资料看看。3 此内容主要来自于维基百科的“二叉查找树”词条 ↩︎ NULL代表该结点为空 ↩︎ 此部分内容主要来自维基百科的“平衡树”词条 ↩︎ |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |